DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.58

On the Approximability of Presidential Type Predicates

Authors: Neng Huang and Aaron Potechin

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract

Given a predicate P: {-1, 1}^k → {-1, 1}, let CSP(P) be the set of constraint satisfaction problems whose constraints are of the form P. We say that P is approximable if given a nearly satisfiable instance of CSP(P), there exists a probabilistic polynomial time algorithm that does better than a random assignment. Otherwise, we say that P is approximation resistant. In this paper, we analyze presidential type predicates, which are balanced linear threshold functions where all of the variables except the first variable (the president) have the same weight. We show that almost all presidential type predicates P are approximable. More precisely, we prove the following result: for any δ₀ > 0, there exists a k₀ such that if k ≥ k₀, δ ∈ (δ₀,1 - 2/k], and {δ}k + k - 1 is an odd integer then the presidential type predicate P(x) = sign({δ}k{x₁} + ∑_{i = 2}^{k} {x_i}) is approximable. To prove this, we construct a rounding scheme that makes use of biases and pairwise biases. We also give evidence that using pairwise biases is necessary for such rounding schemes.

Cite as

Neng Huang and Aaron Potechin. On the Approximability of Presidential Type Predicates. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 58:1-58:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.APPROX/RANDOM.2020.58,
  author =	{Huang, Neng and Potechin, Aaron},
  title =	{{On the Approximability of Presidential Type Predicates}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{58:1--58:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.58},
  URN =		{urn:nbn:de:0030-drops-126612},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.58},
  annote =	{Keywords: constraint satisfaction problems, approximation algorithms, presidential type predicates}
}

Document

DOI: 10.4230/LIPIcs.ESA.2018.45

On the Decision Tree Complexity of String Matching

Authors: Xiaoyu He, Neng Huang, and Xiaoming Sun

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract

String matching is one of the most fundamental problems in computer science. A natural problem is to determine the number of characters that need to be queried (i.e. the decision tree complexity) in a string in order to decide whether this string contains a certain pattern. Rivest showed that for every pattern p, in the worst case any deterministic algorithm needs to query at least n-|p|+1 characters, where n is the length of the string and |p| is the length of the pattern. He further conjectured that this bound is tight. By using the adversary method, Tuza disproved this conjecture and showed that more than one half of binary patterns are evasive, i.e. any algorithm needs to query all the characters (see Section 1.1 for more details). In this paper, we give a query algorithm which settles the decision tree complexity of string matching except for a negligible fraction of patterns. Our algorithm shows that Tuza's criteria of evasive patterns are almost complete. Using the algebraic approach of Rivest and Vuillemin, we also give a new sufficient condition for the evasiveness of patterns, which is beyond Tuza's criteria. In addition, our result reveals an interesting connection to Skolem's Problem in mathematics.

Cite as

Xiaoyu He, Neng Huang, and Xiaoming Sun. On the Decision Tree Complexity of String Matching. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 45:1-45:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.ESA.2018.45,
  author =	{He, Xiaoyu and Huang, Neng and Sun, Xiaoming},
  title =	{{On the Decision Tree Complexity of String Matching}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{45:1--45:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.45},
  URN =		{urn:nbn:de:0030-drops-95082},
  doi =		{10.4230/LIPIcs.ESA.2018.45},
  annote =	{Keywords: String Matching, Decision Tree Complexity, Boolean Function, Algebraic Method}
}

Search Results

Documents authored by Huang, Neng

On the Approximability of Presidential Type Predicates

Abstract

Cite as

On the Decision Tree Complexity of String Matching

Abstract

Cite as

Thanks for your feedback!

Could not send message